# Copyright (c) 2010
# The Regents of the University of Michigan
# All Rights Reserved

# Permission is granted to use, copy, create derivative works, and
# redistribute this software and such derivative works for any purpose,
# so long as the name of the University of Michigan is not used in
# any advertising or publicity pertaining to the use or distribution
# of this software without specific, written prior authorization. If
# the above copyright notice or any other identification of the
# University of Michigan is included in any copy of any portion of
# this software, then the disclaimer below must also be included.

# This software is provided as is, without representation or warranty
# of any kind either express or implied, including without limitation
# the implied warranties of merchantability, fitness for a particular
# purpose, or noninfringement.  The Regents of the University of
# Michigan shall not be liable for any damages, including special,
# indirect, incidental, or consequential damages, with respect to any
# claim arising out of or in connection with the use of the software,
# even if it has been or is hereafter advised of the possibility of
# such damages.

'''
Provides one class: OrderedListSet.

>>> OrderedListSet([1, 2, 3], key=lambda x: x) == [1, 2, 3]
True
'''

import bisect
import collections


class OrderedListSet(collections.MutableSet, collections.Sequence):
  '''Set ordered by a key function.
  
  Uses a list and bisect internally, so insertion is linear time. Sets
  are small in the intended application.
  '''

  def __init__(self, iterable, key):
    self.elts = list(iterable)
    self.keys = map(key, iterable)
    self.elts.sort(key=key)
    self.keys.sort()
    self.key = key

  def __len__(self):
    return len(self.elts)

  def __iter__(self):
    return iter(self.elts)

  def __contains__(self, item):
    item_key = self.key(item)
    idx = bisect.bisect_left(self.keys, item_key)
    return idx < len(self.elts) and self.elts[idx] == item

  def __getitem__(self, idx):
    return self.elts[idx]

  def __delitem__(self, idx):
    del self.elts[idx]
    del self.keys[idx]

  def add(self, item):
    item_key = self.key(item)
    insertion_point = bisect.bisect_left(self.keys, item_key)
    if insertion_point >= len(self.keys) or self.elts[insertion_point] != item:
      self.elts.insert(insertion_point, item)
      self.keys.insert(insertion_point, item_key)

  def discard(self, item):
    item_key = self.key(item)
    insertion_point = bisect.bisect_left(self.keys, item_key)
    if self.elts[insertion_point] == item:
      del self.elts[insertion_point]
      del self.keys[insertion_point]

